package com.c2b.algorithm.leetcode.base;

import java.util.*;

/**
 * <a href="https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/">二叉搜索树的最近公共祖先(Lowest Common Ancestor of a Binary Search Tree)</a>
 * <p>给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。</a>
 * <p><a href="https://baike.baidu.com/item/%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88/8918834?fr=aladdin">最近公共祖先的定义</a>为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1:
 *      输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
 *                                6
 *                             /    \
 *                            <a color='blue'>2</a>      <a color='blue'>8</a>
 *                           / \    / \
 *                          0   4  7   9
 *                             / \
 *                            3   5
 *      输出: 6
 *      解释: 节点 2 和节点 8 的最近公共祖先是 6。
 *
 * 示例 2:
 *      输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
 *                                6
 *                             /    \
 *                            <a color='blue'>2</a>      8
 *                           / \    / \
 *                          0   <a color='blue'>4</a>  7   9
 *                             / \
 *                            3   5
 *      输出: 2
 *      解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
 * </pre>
 * </p>
 * <p>
 * <b>说明:</b>
 * <ul>
 *     <li>所有节点的值都是唯一的。</li>
 *     <li>p、q 为不同节点且均存在于给定的二叉搜索树中。</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @see LC0235LowestCommonAncestorOfABinarySearchTree_M 二叉搜索树的最近公共祖先(Lowest Common Ancestor of a Binary Search Tree)
 * @see LC0236LowestCommonAncestorOfABinaryTree_M 二叉树的最近公共祖先(Lowest Common Ancestor of a Binary Tree)
 * @see LC1644LowestCommonAncestorOfBinaryTree_II_M 二叉树的最近公共祖先 II(Lowest Common Ancestor of a Binary Tree II)
 * @see LC1650LowestCommonAncestorOfBinaryTree_III_M 二叉树的最近公共祖先 III(Lowest Common Ancestor of a Binary Tree III)
 * @since 2023/5/16 9:52
 */
public class LC0235LowestCommonAncestorOfABinarySearchTree_M {

    static class Solution {
        /**
         * 二叉搜索树：左子树的节点值都小于根节点。右子树的节点值都大于根节点。
         */
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null || p == root || q == root) {
                return root;
            }
            TreeNode ancestor = root;
            while (true) {
                if (p.val < root.val && q.val < root.val) {
                    // p、q均在根节点的左侧
                    ancestor = ancestor.left;
                } else if (p.val > root.val && q.val > root.val) {
                    // p、q均在根节点的右侧
                    ancestor = ancestor.right;
                } else {
                    break;
                }
            }
            return ancestor;
        }

        public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null) {
                return null;
            }
            Map<TreeNode, TreeNode> parentMap = new HashMap<>();
            parentMap.put(root, null);
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                TreeNode currNode = queue.poll();
                if (currNode.left != null) {
                    queue.offer(currNode.left);
                    parentMap.put(currNode.left, currNode);
                }
                if (currNode.right != null) {
                    queue.offer(currNode.right);
                    parentMap.put(currNode.right, currNode);
                }
            }
            // p 节点的路径
            List<TreeNode> pPathList = getPath(p, parentMap);
            List<TreeNode> qPathList = getPath(q, parentMap);
            TreeNode ancestor = null;
            for (int i = 0; i < pPathList.size() && i < qPathList.size(); i++) {
                if (pPathList.get(i) == qPathList.get(i)) {
                    ancestor = pPathList.get(i);
                }
            }
            return ancestor;
        }

        private List<TreeNode> getPath(TreeNode node, Map<TreeNode, TreeNode> parentMap) {
            List<TreeNode> path = new ArrayList<>();
            while (node != null) {
                path.add(0, node);
                node = parentMap.get(node);
            }
            return path;
        }
    }
}
